'''
https://www.nowcoder.com/practice/fd55637d3f24484e96dad9e992d3f62e
'''
import sys
from functools import cache

# n, V = map(int, input().split())
# vs, ws = [0] * n, [0] * n
# i = 0
# for line in sys.stdin:
#     vs[i], ws[i] = map(int, line.split())
#     i += 1

n, V = 3, 5
vs, ws = [2, 4, 1], [10, 5, 4]


# dp 记忆化搜索
@cache
def f1(i, rest):
    if i == n:
        return 0
    r1 = f1(i + 1, rest)
    r2 = (f1(i + 1, rest - vs[i]) + ws[i]) if vs[i] <= rest else 0
    return max(r1, r2)

# dp打表
def f2():
    dp = [[0] * (V + 1) for _ in range(n + 1)]
    # 第一维度依赖后边的，第二维度依赖前边的   从下往上，从左往右
    for i in range(n - 1, -1, -1):
        for rest in range(V + 1):
            r1 = dp[i + 1][rest]
            r2 = (dp[i + 1][rest - vs[i]]  + ws[i]) if vs[i] <= rest else 0
            dp[i][rest] = max(r1, r2)
    return dp[0][V]

# dp状态压缩
def f3():
    A = [0] * (V + 1)
    # 第一维度依赖后边的，第二维度依赖前边的   从下往上，从左往右
    for i in range(n - 1, -1, -1):
        B = [0] * (V + 1)
        for rest in range(V + 1):
            r1 = A[rest]
            r2 = (A[rest - vs[i]]  + ws[i]) if vs[i] <= rest else 0
            B[rest] = max(r1, r2)
        A = B
    return A[V]


@cache
def g1(i, rest):
    if i == n:
        return 0 if rest == 0 else -1
    r1 = g1(i + 1, rest)
    r2 = g1(i + 1, rest - vs[i]) if vs[i] <= rest else -1
    if r2 != -1:
        r2 += ws[i]
    return max(r1, r2)

def g2():
    dp = [[-1] * (V + 1) for _ in range(n + 1)]
    # 第一维度依赖后边的，第二维度依赖前边的   从下往上，从左往右
    dp[n][0] = 0
    for i in range(n - 1, -1, -1):
        for rest in range(V + 1):
            r1 = dp[i + 1][rest]
            r2 = (dp[i + 1][rest - vs[i]]) if vs[i] <= rest else -1
            if r2 != -1:
                r2 += ws[i]
            dp[i][rest] = max(r1, r2)
    return dp[0][V]

def g3():
    A = [-1] * (V + 1)
    A[0] = 0
    # 第一维度依赖后边的，第二维度依赖前边的   从下往上，从左往右
    for i in range(n - 1, -1, -1):
        B = [-1] * (V + 1)
        for rest in range(V + 1):
            r1 = A[rest]
            r2 = (A[rest - vs[i]]) if vs[i] <= rest else -1
            if r2 != -1:
                r2 += ws[i]
            B[rest] = max(r1, r2)
        A = B
    return A[V]


# print(f1(0, V))
print(f2())
# res2 = g1(0, V)
res2 = g3()
res2 = 0 if res2 == -1 else res2
print(res2)
